home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / c / pro12 / ssort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-26  |  2.5 KB  |  92 lines
  1. /***********************************************************************/
  2. /*  SORT(): Non-Recursive Shell's Sort function.                       */
  3. /*  See the function declaration for calling information.              */
  4. /* Function is by Bruce Feist; please contact me on CompuServe with    */
  5. /*    a message on BPROGB, MACDEV, or EASYPLEX if you have any         */
  6. /*    questions or problems.                                           */
  7. /* You can also reach me at the Enlightened Board, at (703) 370-9528,  */
  8. /*   N/8/1                                                             */
  9. /* Feel free to make use of this code in your own programs.            */
  10. /***********************************************************************/
  11. /* Shell's sort.  Not bad for intermediate sizes. */
  12. /* Uses increment sequence h(n+1) = 3*h(n) + 1,   */
  13. /* as suggested by Knuth. */
  14.  
  15. #include <alloc.h>
  16. #include <mem.h>
  17. #include <stddef.h>
  18. #include <stdio.h>
  19.  
  20. #include "sort.h"
  21.  
  22. #define VERBOSE (0)
  23.  
  24. static char *base;
  25. static double *dbase;
  26. static int nelem, width;
  27. static int (*compare) (void *, void *);
  28. static int get_increment (int n_elements);
  29. static char *temp_record;
  30.  
  31. int
  32. ssort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
  33. {
  34.   register unsigned int increment;
  35.   long offset;
  36.   register unsigned int equiv_class;
  37.  
  38.   base = pbase;
  39.   dbase = pbase; /* for debugging only */
  40.   nelem = pnelem;
  41.   width = pwidth;
  42.   compare = pcompare;
  43.  
  44.   temp_record = malloc (width);
  45.   if (temp_record == NULL)
  46.     return S_NOMEM;
  47.  
  48.   for (increment = get_increment (nelem);
  49.        increment > 0;
  50.        increment /= 3)
  51.   {
  52.     for (equiv_class = increment;
  53.      equiv_class < nelem;
  54.      equiv_class++)
  55.     {
  56.       memcpy (temp_record, base + equiv_class * width, width);
  57.       for (offset = equiv_class - increment;
  58.        offset >= 0 &&
  59. #pragma warn -sig
  60.          (*compare) (temp_record, base + offset * width) < 0;
  61. #pragma warn .sig
  62.        offset -= increment)
  63.       {
  64. #pragma warn -sig
  65.     memcpy (base + (increment + offset) * width,
  66.         base + offset * width,
  67. #pragma warn .sig
  68.         width);
  69.     }  /* end for offset */
  70.  
  71. #pragma warn -sig
  72.       memcpy (base + (offset + increment) * width, temp_record, width);
  73. #pragma warn .sig
  74.       } /* end for equiv_class */
  75.     } /* end for increment */
  76.  
  77.   return S_OK;
  78.   }  /* end ssort */
  79.  
  80.   int
  81.   get_increment (int n_elements)
  82.   {
  83.     register int inc;
  84.  
  85.     for (inc = 1;
  86.      inc < n_elements;
  87.      inc = 3 * inc + 1)
  88.       ;
  89.  
  90.     return inc > 17 ? inc/9 : 1;
  91.     } /* end get_increment */
  92.